//
// Created by Lenovo on 2024/3/1.
//
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:

    int m,n;
    bool visited1[201][201];
    bool visited2[201][201];
    int go[4][2]={{1,0},{-1,0},{0,-1},{0,1}};

    //逆流而上
    void dfs1(int x,int y,vector<vector<int>>& heights){
        for(int i=0;i<4;i++){
            int nextX=x+go[i][0];
            int nextY=y+go[i][1];
            if(nextX>=0 && nextX<m && nextY>=0 && nextY<n && heights[x][y]<=heights[nextX][nextY] && !visited1[nextX][nextY]){
                visited1[nextX][nextY]=true;
                dfs1(nextX,nextY,heights);
            }
        }
    }

    void dfs2(int x,int y,vector<vector<int>>& heights){
        for(int i=0;i<4;i++){
            int nextX=x+go[i][0];
            int nextY=y+go[i][1];
            if(nextX>=0 && nextX<m && nextY>=0 && nextY<n && heights[x][y]<=heights[nextX][nextY] && !visited2[nextX][nextY]){
                visited2[nextX][nextY]=true;
                dfs2(nextX,nextY,heights);
            }
        }
    }

    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m=heights.size();
        n=heights[0].size();
        for(int i=0;i<m;i++){
            visited1[i][0]=true;
            dfs1(i,0,heights);
            visited2[i][n-1]=true;
            dfs2(i,n-1,heights);
        }
        for(int i=0;i<n;i++){
            visited1[0][i]= true;
            dfs1(0,i,heights);
            visited2[m-1][i]= true;
            dfs2(m-1,i,heights);
        }
        vector<vector<int>> resList;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(visited1[i][j] && visited2[i][j]){
                    resList.push_back({i,j});
                }
            }
        }
        return resList;
    }
};
